
#include "swap.c"

#ifndef SORT_INSERTION
#define SORT_INSERTION

// 从第 P 趟开始继续排
void insertion_Sort_Pass(ElementType a[], int p, int length) {
    ElementType tmp = a[p]; // 下一个待排序的数
    int i;
    for (i=p; i > 0 && comparator(a[i-1], tmp) > 0; i--) {
        a[i] = a[i-1]; // 移出空位
    }
    // 插入
    a[i] = tmp;
}

void insertion_Sort(ElementType a[], int length) {
    // 执行 p-1 次
    for (int p=1; p < length; p++) {
        insertion_Sort_Pass(a, p, length);
    }
}

#endif
